# 05. 多数元素.py
# 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
from typing import List
import collections

class Solution1:
    def majorityElement(self, nums: List[int]) -> int:
        # collections.Counter以O(n)的时间复杂度统计一个list中的每个元素的个数。
        counts = collections.Counter(nums)
        # get函数用于获取counts字典的值。
        # key=关键词是用来获取用于比较的那个值的函数，有点类似于Java的Comparable接口
        return max(counts.keys(), key=counts.get)

class Solution2:
    def majorityElement(self, nums: List[int]) -> int:
        count_dict = {}
        n = len(nums)
        for num in nums:
            if num not in count_dict:
                count_dict[num] = 1
            else:
                count_dict[num] += 1
            if count_dict[num] > n/2:
                return num


if __name__ == '__main__':
    # solution2是蛮力法
    # solution = Solution1()
    # solution1是蛮力法的简化写法
    solution = Solution2()
    nums = [3, 2, 3]
    answer = solution.majorityElement(nums)
    print(answer)